package nowcoder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ReconstructBinaryTree {

	public static void main(String[] args) {
		ReconstructBinaryTree main = new ReconstructBinaryTree();
		
		int[] pre = {1,2,4,7,3,5,6,8};
		int[] in = {4,7,2,1,5,3,8,6};
		
		TreeNode root = main.reConstructBinaryTree(pre, in);
		
		preOrder(root);
		System.out.println();
		inOrder(root);
		System.out.println();
		postOrder(root);
		System.out.println();

		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.addFirst(root);
		main.printByLevel(queue);
		
	}
	
	private static void preOrder(TreeNode root) {
		if(root == null)
			return;
		System.out.print(root.val);
		preOrder(root.left);
		preOrder(root.right);
	}
	
	private static void inOrder(TreeNode root) {
		if(root == null)
			return;
		inOrder(root.left);
		System.out.print(root.val);
		inOrder(root.right);
	}
	
	private static void postOrder(TreeNode root) {
		if(root == null)
			return;
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.val);
	}

	private void printByLevel(LinkedList<TreeNode> queue) {
		LinkedList<TreeNode> newQueue = new LinkedList<>();
		TreeNode node;
		while(!queue.isEmpty()) {
			node = queue.removeFirst();
			System.out.print(node.val + "\t");
			if(node.left != null)
				newQueue.add(node.left);
			if(node.right != null)
				newQueue.add(node.right);
		}
		System.out.println();
		
		if(newQueue.size() > 0)
			printByLevel(newQueue);
	}

	public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		List<Integer> preList = new ArrayList<>();
		for (int integer : pre) {
			preList.add(integer);
		}
		List<Integer> inList = new ArrayList<>();
		for (int integer : in) {
			inList.add(integer);
		}
		
		return reconstruct(preList, inList);
	}

	private TreeNode reconstruct(List<Integer> preList, List<Integer> inList) {
		if(preList.size() == 0)
			return null;
		if(preList.size() == 1)
			return new TreeNode(preList.get(0));
		
		int rootVal = preList.get(0);
		TreeNode root = new TreeNode(rootVal);
		List<Integer> leftPre = new ArrayList<>();
		List<Integer> leftIn = new ArrayList<>();
		
		List<Integer> rightPre = new ArrayList<>();
		List<Integer> rightIn = new ArrayList<>();
		
		int index = inList.indexOf(rootVal);
		for(int i = 0; i < index; i++) {
			leftIn.add(inList.get(i));
		}
		for(int i = index + 1; i < inList.size(); i++) {
			rightIn.add(inList.get(i));
		}
		
		preList.remove(0);
		for(int i = 0; i < leftIn.size(); i++) {
			leftPre.add(preList.get(i));
		}
		for(int i = leftPre.size(); i < preList.size(); i++) {
			rightPre.add(preList.get(i));
		}
		
		root.left = reconstruct(leftPre, leftIn);
		root.right = reconstruct(rightPre, rightIn);
		
		return root;
	}

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}

}
